package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * 118.杨辉三角
 * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 * 输入: numRows = 5
 * 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
 */
public class Num_118 {
    public List<List<Integer>> generate(int numRows) {

        List<List<Integer>> ret = new ArrayList<>();
        //第一行
        List<Integer> first = Arrays.asList(1);
        ret.add(first);
        if(numRows == 1){
            return ret;
        }
        //第二行
        List<Integer> second = Arrays.asList(1,1);
        ret.add(second);
        if(numRows == 2){
            return ret;
        }
        //从第三行开始按规律
        for(int i=3; i<=numRows; i++){
            //找到前一行的列表
            List<Integer> prev = ret.get(i - 1 - 1);
            //定义当前行的列表
            List<Integer> cur = new ArrayList<>();
            cur.add(1);
            for(int j=1; j<i-1; j++){
                cur.add(prev.get(j-1) + prev.get(j));
            }
            cur.add(1);
            //将当前行添加到列表中
            ret.add(cur);
        }
        return ret;
    }
}

